#include <stdio.h>
#include <stdlib.h>

#define VAL_MAX     0x7FFFFFFF

struct node
{
    int val;
    int parent;
    int left;
    int right;
};

int n, m;
struct node *nodes;

static void select_min(int index, int *a, int *b)
{
    int i, min1, min2, tmp;
    
    min1 = min2 = 0;

    for (i = 1; i < index; i++) {
        if (nodes[i].parent == 0 && 
            nodes[i].val < nodes[min1].val) {
            min2 = min1;
            min1 = i;
        }
        else if (nodes[i].parent == 0 &&
            nodes[i].val < nodes[min2].val) {
            min2 = i;
        }
    }

    *a = min1;
    *b = min2;
}

int main(int argc, char const* argv[])
{
    int i, a, b;
    char *bits;
    int start, tmp;

    if (argc == 1)
    {
        printf("usage: %s num1 num2 num3...\n", argv[0]);
        exit(0);
    }

    n = argc-1;
    m = 2*n-1;

    if (n == 1)
    {
        printf("%s\t:%d\n", argv[1], 0);
        exit(0);
    }

    nodes = calloc(sizeof(struct node), m+1);
    bits = malloc(n+1);
    bits[n] = '\0';

    nodes[0].val = VAL_MAX;
    for (i = 1; i <= n; i ++)
        nodes[i].val = atoi(argv[i]);

    for (i = n+1; i <= m; i++) {
        select_min(i, &a, &b);
        nodes[i].left = a;
        nodes[i].right = b;
        nodes[i].val = nodes[a].val + nodes[b].val;
        nodes[a].parent = i;
        nodes[b].parent = i;
    }
    
    for (i = 1; i <= n; i++) {
        tmp = i;
        start = n-1;
        while (nodes[tmp].parent != 0)
        {
            if (nodes[nodes[tmp].parent].left == tmp)
                bits[start] = '0';
            else
                bits[start] = '1';
            start --;
            tmp = nodes[tmp].parent;
        }
        start ++;
        printf("%d\t:%s\n", nodes[i].val, &bits[start]);
    }

    return 0;
}
